package LinkedListOJ;

import java.util.ArrayList;
import java.util.List;

/**
 * Description:
 * Date: 2025-11-09
 * Time: 14:04
 */

class ListNode {
      int val;
      ListNode next;
      ListNode(int x) {
          val = x;
          next = null;
      }
  }

public class Test {

    //环形链表  https://leetcode.cn/problems/linked-list-cycle/
    public boolean hasCycle(ListNode head) {
        /*if (head == null || head.next == null) {
            return false;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                return true;
            }
        }
        return false;*/

        if (head == null || head.next == null) {
            return false;
        }
        List<ListNode> list = new ArrayList<>();
        ListNode cur = head;
        while (cur != null) {
            boolean fal =  list.contains(cur);
            if (fal) {
                return true;
            }
            list.add(cur);
            cur = cur.next;
        }
        return false;
    }

    //环形链表Ⅱ  https://leetcode.cn/problems/linked-list-cycle-ii/description/
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                break;
            }

        }
        if(fast == null || fast.next == null) {
            return null;
        }
        //此时快慢指针的相遇点到环节点的距离等于头节点到环节点的距离
        fast = head;
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
        /*if (head == null || head.next == null) {
            return null;
        }
        List<ListNode> list = new ArrayList<>();
        ListNode cur = head;
        while (cur != null) {
            boolean fal =  list.contains(cur);
            if (fal) {
                return cur;
            }
            list.add(cur);
            cur = cur.next;
        }
        return null;*/
    }

    public static void main(String[] args) {

    }
}
